#include<unordered_map>
#include<unordered_set>;
#include<vector>
#include<string>
#include<thread>
#include<iostream>
using namespace std;
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string>dict;
        for (auto& word : wordDict)dict.insert(word);
        vector<vector<vector<int>>>dp(s.length() + 1);
        dp[0].push_back({ 0 });
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                string str = s.substr(j, i - j);
                if (dict.find(str) == dict.end()) continue;
                for (auto left : dp[j]) {
                    left.push_back(i);
                    dp[i].push_back(left);
                }
            }
        }
        vector<string>res;
        for (int i = 0; i < dp.back().size(); ++i) {
            auto& idx = dp.back()[i];
            string str = "";
            for (int j = 1; j < idx.size(); ++j)
                str += s.substr(idx[j - 1], idx[j] - idx[j - 1]) + ((j == idx.size() - 1) ? "" : " ");
            res.push_back(str);
        }
        return res;
    }
};

int main() {
    string s = "";
    vector<string>wordDict;

}